from random import randrange

class BinaryNode(object):
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
        self.children = [self.left, self.right]
        
    def __repr__(self):
        return "%s" % self.value
    
    def is_leaf(self):
        if self.left is None and self.right is None:
            return True
        return False

#
# Minimax        
class BinaryMinimax(BinaryNode):        
    @classmethod
    def build(cls, node, parent=None, depth=0):
        if node.is_leaf():
            return node
        else:
            left_value = cls.build(node.left, node, depth=depth+1).value
            right_value = cls.build(node.right, node, depth=depth+1).value
            if cls.determine_max(depth):
                if left_value > right_value:
                    node.value = left_value
                else:
                    node.value = right_value
            else:
                if left_value < right_value:
                    node.value = left_value
                else:
                    node.value = right_value
            return node
    
    @classmethod        
    def determine_max(cls, depth):
        if depth % 2 == 0:
            return True
        elif depth % 2 == 1:
            return False

#
# Tree builders
#
                
def just_leaves_tree(num):
    leaves = []
    for i in xrange(num):
        leaves.append(BinaryNode(randrange(-100, 100)))
    
    while len(leaves) > 1:
        left = leaves.pop(0)
        right = leaves.pop(0)
        leaves.append(BinaryNode(left=left, right=right))
        
    root = leaves[0]
    return root    
        
def minimax_tree(root):
    return BinaryMinimax.build(root)